/**
 * 
 */
package edu.umd.clip.lm.util.tree;

import org.w3c.dom.*;
import java.lang.reflect.*;

import edu.umd.clip.lm.model.HistoryTreePayload;
import edu.umd.clip.lm.util.*;
/**
 * @author Denis Filimonov <den@cs.umd.edu>
 *
 */
public class BinaryTree <T extends XMLizable> extends XMLizable {
	private static final long serialVersionUID = 1L;
	public static final String XML_ELEMENT_NAME = "binary-tree";
	public static final String XML_PAYLOAD_NAME = "payload";
	public static final String XML_ATTR_PAYLOAD_CLASS_NAME = "payload-class";
	public static final String XML_LEFT_NODE_NAME = "left";
	public static final String XML_RIGHT_NODE_NAME = "right";
	
	private T payload;
	private BinaryTree<T> left = null;
	private BinaryTree<T> right = null;
	private BinaryTree<T> parent = null;
	
	public BinaryTree(T payload) {
		super();
		this.payload = payload;
	}
	
	public BinaryTree(Element xmlnode) {
		this(xmlnode, null);
	}
	
	@SuppressWarnings("unchecked")
	public BinaryTree(Element xmlnode, Class<? extends T> payloadClass) {
		assert(xmlnode.getTagName().equals(XML_ELEMENT_NAME));
		// get the payload
		{
			Element e = XMLUtils.getFirstElementByTagName(xmlnode, XML_PAYLOAD_NAME);
			if (e == null) {
				this.payload = null;
			} else {
				try {
					String classname = e.getAttribute(XML_ATTR_PAYLOAD_CLASS_NAME);
					if (!classname.isEmpty()) {
						payloadClass = (Class<? extends T>)Class.forName(classname);
					}
					if (payloadClass == null) {
						throw new Exception("BinaryTree: payload class not provided");
					}
					NodeList nodes = e.getChildNodes();
					Constructor<? extends T> construct = payloadClass.getConstructor(Element.class);
					for(int i=0; i<nodes.getLength(); ++i) {
						if (nodes.item(i).getNodeType() == Node.ELEMENT_NODE) {
							Element item = (Element) nodes.item(i);
							this.payload = construct.newInstance(item);
							break;
						}
					}
				} catch(Exception ex) {
					ex.printStackTrace();
					System.exit(0);
				}
			}
		}
		// left branch
		{
			Element e = XMLUtils.getFirstElementByTagName(xmlnode, XML_LEFT_NODE_NAME);
			if (e != null) {
				attachLeft(new BinaryTree<T>(XMLUtils.getFirstElementByTagName(e, XML_ELEMENT_NAME), payloadClass));
			}
		}
		// right branch
		{
			Element e = XMLUtils.getFirstElementByTagName(xmlnode, XML_RIGHT_NODE_NAME);
			if (e != null) {
				attachRight(new BinaryTree<T>(XMLUtils.getFirstElementByTagName(e, XML_ELEMENT_NAME), payloadClass));
			}
		}
	}

	public void attachLeft(BinaryTree<T> left) {
		this.left = left;
		this.left.parent = this;
	}
	
	public void attachRight(BinaryTree<T> right) {
		this.right = right;
		this.right.parent = this;
	}
	
	public BinaryTree<T> removeLeft() {
		BinaryTree<T> l = this.left;
		this.left = null;
		l.parent = null;
		return l;
	}
	
	public BinaryTree<T> removeRight() {
		BinaryTree<T> r = this.right;
		this.right = null;
		r.parent = null;
		return r;
	}

	public boolean isLeaf() {
		return left == null && right == null;
	}
	
	public BinaryTree<T> copy() {
		BinaryTree<T> copy = new BinaryTree<T>(payload);
		if (left != null) {
			copy.attachLeft(left.copy());
		}
		if (right != null) {
			copy.attachRight(right.copy());
		}
		return copy;
	}
	
	public BinaryTree<T> searchPreorder(BinaryTreeFinder<T> finder) {
		if (finder.apply(this)) return this;
		if (left != null) {
			BinaryTree<T> result = left.searchPreorder(finder);
			if (result != null) return result;
		}
		if (right != null) {
			BinaryTree<T> result = right.searchPreorder(finder);
			if (result != null) return result;
		}
		return null;
	}

	public BinaryTree<T> searchPostorder(BinaryTreeFinder<T> finder) {
		if (left != null) {
			BinaryTree<T> result = left.searchPostorder(finder);
			if (result != null) return result;
		}
		if (right != null) {
			BinaryTree<T> result = right.searchPostorder(finder);
			if (result != null) return result;
		}
		if (finder.apply(this)) return this;
		return null;
	}

	public BinaryTree<T> searchToRoot(BinaryTreeFinder<T> finder) {
		if (finder.apply(this)) return this;
		if (parent != null) return parent.searchToRoot(finder);
		return null;
	}
	
	public BinaryTree<T> findNode(BinaryPrefix bits) {
		return findNode(bits, 0);
	}
	
	public BinaryTree<T> findNode(BinaryPrefix bits, int offset) {
		BinaryTree<T> node = this;
		for(int i = offset; i < bits.getSize(); ++i) {
			if (node == null) return null;
			if (bits.get(i)) {
				node = node.right;
			} else {
				node = node.left;
			}
		}
		return node;
	}
	
	public T getPayload() {
		return payload;
	}

	public void setPayload(T payload) {
		this.payload = payload;
	}

	public BinaryTree<T> getLeft() {
		return left;
	}

	public void setLeft(BinaryTree<T> left) {
		this.left = left;
	}

	public BinaryTree<T> getRight() {
		return right;
	}

	public void setRight(BinaryTree<T> right) {
		this.right = right;
	}

	public BinaryTree<T> getParent() {
		return parent;
	}

	public void setParent(BinaryTree<T> parent) {
		this.parent = parent;
	}
	
	public int distanceToRoot() {
		int distance = 0;
		BinaryTree<T> node = this;
		
		while(node.getParent() != null) {
			++distance;
			node = node.getParent();
		}
		return distance;
	}

	/* (non-Javadoc)
	 * @see edu.umd.clip.lm.util.XMLizable#createXML(org.w3c.dom.Document)
	 */
	@Override
	public Element createXML(Document doc) {
		return createXML(doc, null);
	}
	
	@SuppressWarnings("unchecked")
	public Element createXML(Document doc, Class<? extends T> payloadClass) {
		Element element = doc.createElement(XML_ELEMENT_NAME);
		if (payload != null) {
			Element payloadElement = doc.createElement(XML_PAYLOAD_NAME);
			if (!payload.getClass().equals(payloadClass)) {
				payloadElement.setAttribute(XML_ATTR_PAYLOAD_CLASS_NAME, payload.getClass().getCanonicalName());
				
				payloadClass = (Class<T>) payload.getClass();
			}
			payloadElement.appendChild(payload.createXML(doc));
			element.appendChild(payloadElement);
		}
		if (this.left != null) {
			Element leftElement = doc.createElement(XML_LEFT_NODE_NAME);
			leftElement.appendChild(this.left.createXML(doc, payloadClass));
			element.appendChild(leftElement);
		}
		if (this.right != null) {
			Element rightElement = doc.createElement(XML_RIGHT_NODE_NAME);
			rightElement.appendChild(this.right.createXML(doc, payloadClass));
			element.appendChild(rightElement);
		}
		return element;
	}
	
	/* (non-Javadoc)
	 * @see edu.umd.clip.lm.util.XMLizable#getElementName()
	 */
	@Override
	public String getElementName() {
		return XML_ELEMENT_NAME;
	}

	public BinaryTreeIterator<T> getPostOrderIterator() {
		return new PostOrderIterator<T>(this);
	}

	public BinaryTreeIterator<T> getPreOrderIterator() {
		return new PreOrderIterator<T>(this);
	}

	public BinaryTreeIterator<T> getLeafIterator() {
		return new LeafIterator<T>(this);
	}
	
	private static class LeafIterator<T extends XMLizable> extends PostOrderIterator<T> {
		public LeafIterator(BinaryTree<T> root) {
			super(root);
		}

		public boolean hasNext() {
			while (current != null && !current.isLeaf()) {
				nextNode();
			}
			return current != null;
		}
	}
	
	private static class PreOrderIterator<T extends XMLizable> extends BinaryTreeIterator<T> {

		public PreOrderIterator(BinaryTree<T> root) {
			super(root);
		}

		public boolean hasNext() {
			return current != null;
		}

		protected BinaryTree<T> findNextLeaf(BinaryTree<T> item) {
			BinaryTree<T> lastItem = null;
			while((item.right == null || item.right == lastItem) && item != root) {
				lastItem = item;
				item = item.parent;
			}
			return lastItem == item.right ? null : item.right;
		}

		/* (non-Javadoc)
		 * @see edu.umd.clip.lm.util.tree.BinaryTreeIterator#nextNode()
		 */
		@Override
		public BinaryTree<T> nextNode() {
			BinaryTree<T> node = current;
			if (current.left != null) {
				current = current.left;
			} else {
				current = findNextLeaf(current);
			}
			return node;
		}		
	}
	
	private static class PostOrderIterator<T extends XMLizable> extends BinaryTreeIterator<T> {

		public PostOrderIterator(BinaryTree<T> root) {
			super(root);
			current = findNextLeaf(root);
		}

		public boolean hasNext() {
			return current != null;
		}

		protected static <T extends XMLizable> BinaryTree<T> findNextLeaf(BinaryTree<T> item) {
			while(!item.isLeaf()) {
				while(item.left != null) {
					item = item.left;
				}
				
				if (item.right != null) {
					item = item.right; 
				}
			}
			return item;
		}

		/* (non-Javadoc)
		 * @see edu.umd.clip.lm.util.tree.BinaryTreeIterator#nextNode()
		 */
		@Override
		public BinaryTree<T> nextNode() {
			BinaryTree<T> node = current;
			if (current.parent != null && current.parent.left == current) {
				if (current.parent.right != null) {
					current = findNextLeaf(current.parent.right);
				} else {
					current = current.parent;
				}
			} else {
				current = current.parent;
			}
			if (node == root) current = null;
			return node;
		}
	}
}
